package com.wang.utils.sort;

import java.util.Arrays;

/**
 * @author 86173
 * @date 2021/7/30 18:39
 */

/**
 * 看做一个有序的数组和无序的数组
 * 把无序数组中的值一次插到有序数组中
 * 开始有序的大小为1 只有一个元素
 * 无序的大小为n-1
 */
public class InsertSort {

	public static void main(String[] args) {

	}

	public int[] sort(int[] sourceArray) throws Exception {
		// 对 arr 进行拷贝，不改变参数内容
		int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
		int tmp = 0;
		int j = 0;
		// 从下标为1的元素开始选择合适的位置插入，因为下标为0的只有一个元素，默认是有序的
		for (int i = 1; i < arr.length; i++) {

			// 记录要插入的数据
			tmp = arr[i];

			// 从已经排序的序列最右边的开始比较，找到比其小的数
			j = i;
			while (j > 0 && tmp < arr[j - 1]){//j>0是一个界限条件
				arr[j] = arr[j - 1];
				j--;
			}

			// 存在比其小的数，插入  是否需要赋值，如果是他的实际位置就不动
			if (j != i) {
				arr[j] = tmp;
			}

		}
		return arr;
	}
}
